//n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 
//
// 上图为 8 皇后问题的一种解法。 
//
// 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 
//
// 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 示例: 
//
// 输入: 4
//输出: [
// [".Q..",  // 解法 1
//  "...Q",
//  "Q...",
//  "..Q."],
//
// ["..Q.",  // 解法 2
//  "Q...",
//  "...Q",
//  ".Q.."]
//]
//解释: 4 皇后问题存在两个不同的解法。
// 
//
// 
//
// 提示： 
//
// 
// 皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步
//，可进可退。（引用自 百度百科 - 皇后 ） 
// 
// Related Topics 回溯算法


package leetcode.editor.cn;

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P51NQueens {
    static int num = 0;

    public static void main(String[] args) {
        Solution solution = new P51NQueens().new Solution();
        //TO TEST
//        solution.solveNQueens(4);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> result = new ArrayList<>();
            boolean[] use = new boolean[n];
            int[] arr = new int[n];
            indexAll(arr, 0, result);
//            result.forEach(System.out::println);
            return result;
        }

        /**
         * 放置所有棋子的方案
         * @param arr 记录每行放置棋子的坐标
         * @param row 已经放置到第几行
         * @param result 结果集
         */
        void indexAll(int[] arr, int row, List<List<String>> result) {
            //计算该行 不可放置棋子的位置
            boolean[] use = new boolean[arr.length];
            for (int i = 0; i < row; i++) {
                use[arr[i]] = true; //正下方
                if(arr[i] + i - row >= 0){ //左斜角
                    use[arr[i] + i - row] = true;
                }
                if(arr[i] - i + row < arr.length){ //右斜角
                    use[arr[i] - i + row] = true;
                }
            }
            //对可放置棋子的位置进行递归
            for (int i = 0; i < use.length; i++) {
                if (!use[i]) {
                    arr[row] = i;
                    row++;
                    use[i] = true;
                    if (row == use.length) {
//                        System.out.println((++num) + " : " + Arrays.toString(arr));
                        List<String> r = new ArrayList<>(use.length);
                        for (int ite : arr) {
                            r.add(indexQueens(ite, use.length));
                        }
                        result.add(r);
                    }
                    indexAll(arr, row, result);
                    use[i] = false;
                    row--;
                }
            }

        }

        /**
         * 打印棋子 字符串；例如 .Q..
         * @param index 棋子坐标
         * @param n 多少列
         * @return
         */
        String indexQueens(int index, int n) {
            char[] row = new char[n];
            for (int i = 0; i < n; i++) {
                if (i == index) {
                    row[i] = 'Q';
                } else {
                    row[i] = '.';
                }
            }
            return new String(row);
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

}